ArrayList 和 LinkedList 的区别

在 Java 中，ArrayList 和 LinkedList 都是实现了 List 接口的类，这意味着它们都保证元素的顺序。

# 实现方式

1. ArrayList： ArrayList 基于动态数组实现。

• 它维护一个内部数组，当元素增加时，如果数组容量不足，ArrayList 会创建一个更大的新数组并将旧数组的元素复制到新数组中。
• 它提供了对元素的快速随机访问（通过索引进行访问），查询访问元素的时间复杂度为 O(1)。由于它是基于数组的，所以它保证了元素的插入顺序，即元素以它们插入的顺序存储和访问。

2. LinkedList： LinkedList 基于双向链表实现。

• 每个元素（节点）包含对前一个和后一个元素的引用。
• 由于没有索引下标，因此查询访问元素的时间复杂度为 O(n)，因为需要从头节点或者尾节点开始遍历到指定位置。它在插入和删除操作上比 ArrayList 更高效（特别是在列表中间插入和删除元素时）。同样，它也保证了元素的插入顺序。

# 内存使用

1. ArrayList：

• 内部数组存储所有元素，因此相对紧凑。
• 在扩容时，可能会浪费一些内存，因为新数组可能比实际需要的空间大一些（通常新容量是旧容量的 1.5 倍）。

2. LinkedList：

• 每个节点除了存储元素外，还存储两个引用（前一个和后一个节点），因此相比于 ArrayList，LinkedList 的内存开销更大。

# 插入和删除操作

1. ArrayList：

• 在末尾添加或删除元素的时间复杂度为 O(1)。如果数组已满，需要扩容，则添加的时间复杂度为O(n)。
• 在中间位置插入或删除元素的时间复杂度为 O(n)，因为需要移动后续的所有元素。

2. LinkedList：

• 在开头或结尾添加或删除元素的时间复杂度为 O(1)。
• 在中间位置插入或删除元素的时间复杂度为 O(n) + O(1)，因为需要遍历到指定位置，但不需要移动元素，只需调整引用。

# 详细说明

ArrayList:

• 优点：随机访问快，查找元素速度快（时间复杂度为 O(1)）。
• 缺点：插入和删除元素时，如果不是在末尾进行，效率较低，因为这些操作可能需要移动大量元素（时间复杂度为 O(n)）。
• 用途：适合频繁读取但不经常修改内容的场景。

LinkedList:

• 优点：插入和删除操作速度快，尤其是在列表的两端或中间进行操作时（时间复杂度为 O(1) 对于头部和尾部操作）。
• 缺点：随机访问速度较慢（时间复杂度为 O(n)），因为需要通过节点一个一个地遍历。
• 用途：适合频繁插入、删除操作的场景。

# 示例代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        // ArrayList example
        List<String> arrayList = new ArrayList<>();
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        System.out.println("ArrayList: " + arrayList);

        // LinkedList example
        List<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        System.out.println("LinkedList: " + linkedList);
    }
}

上述示例中，无论是 ArrayList 还是 LinkedList，都会按插入顺序存储和输出元素。

# 总结

ArrayList 是基于动态数组实现的。在执行查询操作时，只需要访问数组下标就可以拿到这个数据，也就是访问该数组的索引，所以非常快，时间复杂度为 O(1)，但是因为其数据结构为动态数组，所以我们在执行数据的删改操作时，我们要维护每个数组的下标（索引），所以比较慢，时间复杂度为 O(n)。

LinkedList 是基于双向链表实现的，因为要维护每个数据的节点指针，因此比较占用空间。在执行查询操作时，由于没有索引，需要从头开始找，所以比较慢，时间复杂度为 O(n)，但是因为其数据结构为双向链表，所以我们在执行数据的删改操作时，我们只需要修改当前节点指针的指向，所以非常快，时间复杂度为 O(1)。